
//最长递增子序列的个数
int LongestNum(vector<int> v)
{
	int size = v.size();
	vector<int> dp(size, 0);
	vector<int> cnt(dp);   //cnt[i]代表以i位置结尾的最长递增子序列的个数
	dp[0] = cnt[0] = 1;
	vector<int> tmp;
	for (int i = 1;i < size;++i)
	{
		int max_length = 0;
		for (int j = i - 1;j >= 0;++j)
		{
			if (dp[i] > dp[j])
			{
				if (dp[j] > max_length)
				{
					tmp.clear();
					tmp.push_back(j);
					max_length = dp[j];
				}
				else if (dp[j] == max_length)
				{
					tmp.push_back(j);
				}
			}
		}
		dp[i] = max_length + 1;
		if (!tmp.empty())
		{
			for (const auto& e : tmp)
			{
				cnt[i] = cnt[e];
			}
		}
		else
		{
			cnt[i] = 1;
		}
	}
	int max_val = INT_MIN;
	for (int i = 0;i < size;++i)
	{
		max_val = std::max(max_val, dp[i]);
	}
	int res = 0;
	for (int i = 0;i < size;++i)
	{
		if (dp[i] == max_val)
		{
			res += cnt[i];
		}
	}
	return res;
}

//奇数在前偶数在后  （相对顺序不变）
void Sort(vector<int>& v)
{
	int front = 0, back = 0;
	int size = v.size();
	while (back < size)
	{
		if (v[back] & 1) //是奇数
		{
			int index = back;
			while (index - 1 >= front)
			{
				v[index] = v[index - 1];
				--index;
			}
			v[front] = v[back];
			++front;
		}
		++back;
	}
}